package 周赛;

public class 判断单词能否放入填字游戏中 {

    public boolean placeWordInCrossword(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j]=='#')
                    continue;
                return dfs(board,i,j,word,0);
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, int i, int j, String word,int num) {
        if (i<0 || i>=board.length || j<0 || j>=board[0].length || board[i][j]=='#')
            return false;
        if (num==word.length()-1)
             return true;
        char c = board[i][j];
        if (board[i][j]==' '|| board[i][j]==word.charAt(num)){
            num++;
            board[i][j]=word.charAt(num);
            if (dfs(board, i, j+1, word, num) || dfs(board, i+1, j, word, num))
                return true;
            num--;
            board[i][j]=c;
        }
        return false;
    }
}
